//
// Created by Jisam on 2024/6/19.
//
#include <bits/stdc++.h>

using i64 = long long;

using namespace std;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }

    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    // 初始化两个数组，a用于存储输入的元素，inva用于存储a中每个元素的逆序索引
    vector<int> a(n), inva(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        inva[a[i]] = i;
    }

    // 初始化动态规划数组f，用于记录每个位置的最小索引
    vector<vector<int>> f(n);
    for(int i = 0; i < n ; i++){
        // 计算当前位置的最小索引t，考虑边界情况和a[i]是否为0
        int t = min(i, a[i] == 0 ? 0 :inva[a[i] - 1] + 1);
        f[t].push_back(i);
    }

    // 初始化答案变量
    i64 ans = 0;

    // 使用Fenwick树来高效计算前缀和
    Fenwick<int> fen(n);
    for (int i = 0; i < n; i++) {
        // 对f[i]中的每个索引j，更新Fenwick树中a[j]位置的值
        for (auto j: f[i]) {
            fen.add(a[j], 1);
        }
        // 因为Fenwick树是前缀和，所以需要减去当前元素的贡献，以保持平衡
        fen.add(a[i],-1);
        // 累加从上一个元素的下一个位置到当前位置的最大的前缀和，作为答案的一部分
        ans += max(0,fen.rangeSum(i == 0 ? 0 : a[i - 1] + 1,a[i]));
    }
    // 输出最终答案
    cout << ans << "\n";

    return 0;

}